package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/">二叉搜索树的第k大节点</a>
 * <p>给定一棵二叉搜索树，请找出其中第 k 大的节点的值。</p>
 * <pre>
 * 示例 1:
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 4
 *
 *
 * 示例 2:
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 *        5
 *       / \
 *      3   6
 *     / \
 *    2   4
 *   /
 *  1
 * 输出: 4
 *
 *
 * 限制：1 ≤ k ≤ 二叉搜索树元素个数
 * </pre>
 *
 * @author c2b
 * @since 2023/4/7 11:21
 */
public class JzOffer0054KthLargest_S {

    /**
     * 因为是二叉搜索树，中序遍历可以使树中的节点有序
     * <p>
     * 左、根、右的中序遍历是按照递增的顺序排序的，所有需要的使中序遍历的逆序（右根左的顺序）
     * </p>
     */
    public int kthLargest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currNode = root;
        List<Integer> list = new ArrayList<>();
        while (currNode != null || !stack.empty()) {
            // 向右找到最右节点
            while (currNode != null) {
                stack.push(currNode);
                currNode = currNode.right;
            }
            currNode = stack.pop();
            list.add(currNode.val);
            currNode = currNode.left;
        }
        return list.get(k - 1);
    }


    public int kthLargest2(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        return list.get(k - 1);
    }

    private void dfs(TreeNode currentNode, List<Integer> list) {
        if (currentNode == null) {
            return;
        }
        // 右
        dfs(currentNode.right, list);
        // 根
        list.add(currentNode.val);
        // 左
        dfs(currentNode.left, list);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(4);
        node.left = new TreeNode(2);
        node.right = new TreeNode(7);
        node.left.left = new TreeNode(1);
        node.left.right = new TreeNode(3);
        node.right.left = new TreeNode(6);
        node.right.right = new TreeNode(9);
        JzOffer0054KthLargest_S jzOffer0054KthLargest_s = new JzOffer0054KthLargest_S();
        System.out.println(jzOffer0054KthLargest_s.kthLargest2(node, 3));
    }
}
